//给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
//
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
//
//
//
//
// 示例 1：
//
//
//输入：n = 12
//输出：3
//解释：12 = 4 + 4 + 4
//
// 示例 2：
//
//
//输入：n = 13
//输出：2
//解释：13 = 4 + 9
//
//
//
// 提示：
//
//
// 1 <= n <= 10⁴
//
//
// Related Topics 广度优先搜索 数学 动态规划 👍 1675 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function numSquares(n: number): number {

    const goodsNum: number = Math.floor(Math.sqrt(n));
    const dp: number[] = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    //? 实际上思路一样 简化了大量无效搜索
    for (let i = 1; i <= goodsNum; i++) {
        const tempVal: number = i * i;
        for (let j = tempVal; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - tempVal] + 1);
        }
    }
    return dp[n];
};
//leetcode submit region end(Prohibit modification and deletion)
